package com.flx.ark.algo;

import lombok.AllArgsConstructor;
import lombok.NoArgsConstructor;

import java.io.InputStream;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * @Author Fenglixiong
 * @Create 2021/12/4 0:01
 * @Description 翻转链表
 * 1.给定一个链表，将链表逆序输出
 * 思路：创建一个新的链表，然后遍历原来的链表，采用头插法将旧链表的数据一个个插入新链表
 **/
public class ReverseLinkedList {

    public static void main(String[] args) {

        Node old = null;
        //1.创建一个链表
        old = headCreate(Arrays.asList(1,2,3,4,5));//头插法
//        old = tailCreate(Arrays.asList(1,2,3,4,5));//尾插法
        //2.输出链表
        showLink(old);
        //3.翻转链表
        Node p = null;//新链表
        Node c = old;//旧链表
        while (c!=null){
            Node t = c.next;//保存旧链表
            c.next = p;//将当前节点指向新链表
            p = c;//新链表头结点指向表头
            c = t;//旧链表指针后移
        }
        //输出链表
        showLink(p);
    }

    /**
     * 头插法插入链表
     * @param argList
     * @return
     */
    public static Node headCreate(List<Integer> argList){
        Node p = null;
        for(Integer x:argList){
            Node t = new Node(x);
            t.next = p;
            p = t;
        }
        return p;
    }

    /**
     * 尾插法插入链表
     * @param argList
     * @return
     */
    public static Node tailCreate(List<Integer> argList){
        Node p = null;
        Node tail = null;
        for (Integer x:argList){
            Node t = new Node(x);
            if(p==null){
                p = tail = t;
            }else {
                tail.next = t;
                tail = t;
            }
        }
        return p;
    }

    /**
     * 输出链表内容
     * @param head
     */
    public static void showLink(Node head){
        Node out = head;
        while (out!=null){
            Node t = out;
            System.out.print(t.value+",");
            out = t.next;
        }
        System.out.println("-------------------------");
    }

    @NoArgsConstructor
    @AllArgsConstructor
    public static class Node{
        public Node(Integer value){
            this.value = value;
        }
        private Integer value;
        private Node next;
    }

}
